;;; Maximum path sum I

;;; Problem 18

;;; By starting at the top of the triangle below and moving
;;; to adjacent numbers on the row below, the maximum total
;;; from top to bottom is 23.

;;; 3
;;; 7 4
;;; 2 4 6
;;; 8 5 9 3

;;; That is, 3 + 7 + 4 + 9 = 23.

;;; Find the maximum total from top to bottom of the
;;; triangle below:

;;; 75
;;; 95 64
;;; 17 47 82
;;; 18 35 87 10
;;; 20 04 82 47 65
;;; 19 01 23 75 03 34
;;; 88 02 77 73 07 63 67
;;; 99 65 04 28 06 16 70 92
;;; 41 41 26 56 83 40 80 70 33
;;; 41 48 72 33 47 32 37 16 94 29
;;; 53 71 44 65 25 43 91 52 97 51 14
;;; 70 11 33 28 77 73 17 78 39 68 17 57
;;; 91 71 52 38 17 14 91 43 58 50 27 29 48
;;; 63 66 04 68 89 53 67 30 73 16 69 87 40 31
;;; 04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

;;; NOTE: As there are only 16384 routes, it is possible to
;;; solve this problem by trying every route. However,
;;; Problem 67, is the same challenge with a triangle
;;; containing one-hundred rows; it cannot be solved by
;;; brute force, and requires a clever method! ;o)

;;; -------------------------------------------------------

;; THOUGHT: It might not result in the maximum sum, if one
;; adds up in a greedy way, always choosing the highest
;; number of the neighhbors. As the problem indicates, there
;; should be a more intelligent way than brute-forcing the
;; problem using backtracking over all paths through the
;; triangle.

;; IDEA: Maybe one can sort the numbers by size and try to
;; take the path, which leads to summing most of the highest
;; numbers? But what if they are not on possible paths?

;; IDEA: Do not calculate sum, but calculate loss and
;; minimize that! -- Failed. Optimizing for loss does not
;; result in the maximum sum.

;; IDEA: Brute-force it, to check, whether an idea of
;; getting to maximum sum works. -- Done!

;; IDEA: Maybe one can solve it bottom up? Discarding paths,
;; which are safe to have not the maximum?




;; IDEA: Choose next number by looking at both next numbers
;; and checking, how they relate to all numbers in the lost
;; numbers:

;; 75

;; -- must choose 95 or 64, which have a difference of 31

;; 95 64

;; -- choosing 64 looses 31 -- Can this be justified by the
;; numbers, which were NOT lost, preserved, by choosing 64?

;; These numbers are: 64 82 10 65 34 67 92 33 29 14 57 48 31
;; 23 -> 649, or without 64 -> 585.

;; Had we chosen 95 instead, the preserved numbers would be:
;; 95 | 17 18 20 19 88 99 41 41 53 70 91 63 04 -> 95 + 624

;; The difference between the numbers 95 and 64, 31, cannnot
;; be justified by the difference of the sum for the
;; preserved path when choosing 64 and the preserved path
;; when choosing 95. -> choose 95

;; Step 2: down 17, right 47 -> right +30
;; Sums of paths difference:
;; right: 87 47 03 63 70 70 94 51 17 29 40 04 -> 575
;; down:  18 20 19 88 99 41 41 53 70 91 63 04 -> 607 -> +32
;; going down justifies the loss of 30 -> choose 17.

;; Step 3: down 18, right 35 -> right +17
;; Sums of paths difference:
;; right: 82 75 07 16 80 16 97 68 27 87 60 -> 615 -> +26
;; down:  20 19 88 99 41 41 53 70 91 63 04 -> 589
;; going down does not justify the loss of 17 -> choose 35.

;; Step 4: down 04, right 82 -> right +78
;; Sums of paths difference:
;; right: 75 07 16 80 16 97 68 27 87 00 -> 473 -> +35
;; down : 01 02 65 41 48 71 11 71 66 62 -> 438
;; going down does not justify the loss of 78 -> choose 82.

;; Algorithm:

;; down_advantage = down - right              (positive? -> down > right)
;; down_sum_advantage = down_sum - right_sum  (positive? -> down_sum > right_sum)
;; if both positive? -> go down
;; if both negative? -> go right
;; if (down_advantage + down_sum_advantage > 0) -> go down
;; if (down_advantage + down_sum_advantage < 0) -> go right
;; if (down_advantage + down_sum_advantage = 0) -> ???

;;; 75
;;; 95 64
;;; 17 47 82
;;; 18 35 87 10
;;; 20 04 82 47 65
;;; 19 01 23 75 03 34
;;; 88 02 77 73 07 63 67
;;; 99 65 04 28 06 16 70 92
;;; 41 41 26 56 83 40 80 70 33
;;; 41 48 72 33 47 32 37 16 94 29
;;; 53 71 44 65 25 43 91 52 97 51 14
;;; 70 11 33 28 77 73 17 78 39 68 17 57
;;; 91 71 52 38 17 14 91 43 58 50 27 29 48
;;; 63 66 04 68 89 53 67 30 73 16 69 87 40 31
;;; 04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

(import
 (except (rnrs base) let-values map)

 (only (guile)
       lambda* λ
       ;; printing
       display
       simple-format)

 (ice-9 textual-ports)
 (ice-9 match)  ; let-match

 (srfi srfi-1)
 ;; for functional structs (not part of srfi-9 directly)
 (srfi srfi-9 gnu)

 (lib fileio)
 (lib list-helpers)
 (lib function-combinators))


;; ======================
;; DATA ABSTRACTION LAYER
;; ======================

;; for positions being a pair of row and column

(define position-row
  (λ (pos)
    (car pos)))

(define position-col
  (λ (pos)
    (cdr pos)))

(define make-position
  (λ (row col)
    (cons row col)))

(define in-triangle?
  (λ (triangle pos)
    (match-let ([(height width) (triangle-dimensions triangle)]
                [(row . col) pos])
      (let ([max-col-ind
             ;; -1 for being a col index, not a width
             (-
              ;; -x for the triangle getting thinner towards the top. substract
              ;; from the width.
              (- width
                 ;; an additional substractions of 1, for being a row index,
                 ;; which starts at 0
                 (-
                  ;; -x, because the higher we get the lower the row index and
                  ;; the more we need to substract from the width
                  (- height row)
                  1))
              1)])
        (and (>= col 0)
             (<= col max-col-ind)
             (array-in-bounds? triangle
                               (position-row pos)
                               (position-col pos)))))))

(define triangle-ref
  (λ (triangle pos)
    (array-ref triangle
               (position-row pos)
               (position-col pos))))


(define triangle-height
  (λ (triangle)
    (match-let ([(rows cols) (array-dimensions triangle)])
      rows)))


(define triangle-width
  (λ (triangle)
    (match-let ([(rows cols) (array-dimensions triangle)])
      cols)))


(define triangle-dimensions
  (λ (triangle)
    (array-dimensions triangle)))


;; functions for getting the next numbers

(define down-neighbor
  (λ (pos)
    (make-position
     (+ (position-row pos) 1)
     (position-col pos))))

(define down-right-neighbor
  (λ (pos)
    (make-position
     (+ (position-row pos) 1)
     (+ (position-col pos) 1))))

;; (define neighbors
;;   (λ (pos)
;;     (list (down-neighbor pos)
;;           (down-right-neighbor pos))))

(define go-down
  (λ (pos)
    (down-neighbor pos)))

(define go-down-right
  (λ (pos)
    (down-right-neighbor pos)))


;; First implement the brute force algorithm.

;; (define maximize
;;   (lambda* (measure
;;             next-args
;;             init-args
;;             stop-condition
;;             #:key (choose max) (stop-value 0))
;;     "The maximize function draws out maximization logic into
;; a separate function.

;; MEASURE calculates a value for some arguments. NEXT-ARGS
;; takes the current arguments and calculates the "
;;     ;; measure calculates a result for some arguments
;;     ;; next proc supplies a list of lists of the arguments for the measure function
;;     ;; init is an initial value for arguments to measure
;;     ;; choose is the function, that chooses the maximum of the results of measure applied to the arguments provided by next.
;;     ))

(define find-max-sum-brute-force
  (λ (triangle)
    (let max-sum ([pos (make-position 0 0)])
      (let ([num-at-pos (triangle-ref triangle pos)])
        (let ([next-down-pos (go-down pos)]
              [next-down-right-pos (go-down-right pos)])
          ;; Add the number at the current position to the maximum sum
          ;; of the smaller triangles, reducing the problem one number
          ;; at a time.
          (+ num-at-pos
             ;; Of the 2 smaller triangles choose to add the one,
             ;; which has the maximum sum. Stop, if the position would
             ;; not be in bounds of the triangle any longer, by using
             ;; 0 as argument to max.
             (max (if (in-triangle? triangle next-down-pos)
                      (max-sum next-down-pos)
                      0)
                  (if (in-triangle? triangle next-down-right-pos)
                      (max-sum next-down-right-pos)
                      0))))))))


(define sum-path
  (λ (triangle initial-pos step)
    (let iter ([pos initial-pos] [sum 0])
      (cond
       [(in-triangle? triangle pos)
        (iter (step pos)
              (+ sum (triangle-ref triangle pos)))]
       [else sum]))))


(define calc-loss
  (λ (triangle pos not-used-move)
    "Calculate the loss, when going from POS to the next
number in the triangle. NOT-USED-MOVE is the function, that
was not used to move to the next number."
    (cond
     [(in-triangle? triangle pos)
      (sum-path triangle
                (not-used-move pos)
                not-used-move)]
     [else 0])))


(define find-max-sum-based-on-loss
  (λ (triangle)
    (let max-sum ([pos (make-position 0 0)])
      (cond
       [(in-triangle? triangle pos)
        (let ([num-at-pos (triangle-ref triangle pos)]
              [loss-moving-down (calc-loss triangle pos go-down-right)]
              [loss-moving-down-right (calc-loss triangle pos go-down)])
          (display (simple-format #f "chose number: ~a\n" num-at-pos))
          ;; (display (simple-format #f "loss down: ~a\n" loss-moving-down))
          ;; (display (simple-format #f "loss down right: ~a\n" loss-moving-down-right))
          (+ num-at-pos
             ;; MAYBE PROBLEM: But what if the loss is equal?
             (cond
              [(< loss-moving-down loss-moving-down-right)
               (max-sum (go-down pos))]
              [(> loss-moving-down loss-moving-down-right)
               (max-sum (go-down-right pos))]
              [(= loss-moving-down loss-moving-down-right)
               (display (simple-format #f "loss down = loss down right\n"))
               (max-sum (go-down pos))])))]
       [else 0]))))


(define find-max-sum-based-on-loss-2
  (λ (triangle)
    (let max-sum ([pos (make-position 0 0)])
      (cond
       [(in-triangle? triangle pos)
        (let ([num-at-pos (triangle-ref triangle pos)]
              [next-down-pos (go-down pos)]
              [next-down-right-pos (go-down-right pos)])
          (display (simple-format #f "chose number: ~a\n" num-at-pos))
          (cond
           [(and (in-triangle? triangle next-down-pos)
                 (in-triangle? triangle next-down-right-pos))
            (let* ([down-advantage
                    (- (triangle-ref triangle next-down-pos)
                       (triangle-ref triangle next-down-right-pos))]
                   [down-sum-advantage
                    (- (sum-path triangle next-down-pos go-down)
                       (sum-path triangle next-down-right-pos go-down-right))])
              (+ num-at-pos
                 (if (>= (+ down-advantage down-sum-advantage) 0)
                     (max-sum next-down-pos)
                     (max-sum next-down-right-pos))))]
           ;; If we are at the bottom of the triangle, the
           ;; maximum sum is the number at the current
           ;; position.
           [else num-at-pos]))]
       [else 0]))))

;; read in the data

(define input-lines
  (get-lines-from-file
   (string-join (list (dirname (current-filename)) "018-input.txt")
                "/")))
(define input
  (let* ([as-list-of-lists
          (map (combine (λ (line) (string-split line (λ (c) (char=? c #\space))))
                        (λ (num-strs) (map string->number num-strs)))
               input-lines)]
         [max-width
          (fold (λ (acc elem) (max elem acc))
                0
                (map length as-list-of-lists))]
         [padded-list-of-lists
          (map (λ (lst) (list-right-pad lst max-width 0))
               as-list-of-lists)]
         [as-array
          (list->array '(0 0) padded-list-of-lists)])
    as-array))


(display
 (simple-format
  #f "max sum (brute force): ~a\n"
  (find-max-sum-brute-force input)))

(display
 (simple-format
  #f "max sum (loss based): ~a\n"
  (find-max-sum-based-on-loss input)))

(display
 (simple-format
  #f "max sum (loss2 based): ~a\n"
  (find-max-sum-based-on-loss-2 input)))
